/*
 * 
 * String/KMP Template
 * BY:uncle-lu
 * 2017-08-07
 * help: get_Next(s为模式串,next为next数组)
 *		 KMP(s为模式串,p为文本串)返回在文本串中第一个匹配到的模式串的位置.
 */


#include<cstring>

void get_Next(char* s ,int next[])
{
	int j=0;
	int k=-1;
	int Len=strlen(s);
	next[0]=-1;
	while(j<Len-1)
	{
		if(k==-1||s[j]==s[k])
		{
			k++;
			j++;
			next[j]=k;
		}
		else 
		{
			k=next[k];
		}
	}
	return ;
}

int KMP(char *s,char *p,int next[])
{
	int Len_s=strlen(s);
	int Len_p=strlen(p);
	int i=0,j=0;
	while(i<Len_s&&j<Len_p)
	{
		if(i==-1||s[i]==p[j])
		{
			i++;
			j++;
		}
		else
		{
			i=next[i];
		}
	}
	if(i==Len_s)return j-i;
	else return -1;
}
